#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSessions(vector<int>& tasks, int sessionTime) {
        int n = tasks.size();
        vector<bool>flag(1 << n, false);
        for(int mask = 1; mask < (1 << n); mask++){
            int need_time = 0;
            for(int i = 0; i < n; i++){
                if(mask & (1 << i))need_time += tasks[i];
                if(need_time > sessionTime)break;
            }
            if(need_time <= sessionTime)flag[mask] = true;
        }

        vector<int>ans(1 << n, 0x3f3f3f3f);
        ans[0] = 0;
        for(int i = 1; i < (1 << n); i++){//对于所有的状态
            for(int sub = i; sub; sub = (sub - 1) & i){//枚举子集
                if(flag[sub])ans[i] = min(ans[i], ans[i ^ sub] + 1);
            }
        }
        return ans[(1 << n) - 1];
    }
};

/**
 * 2021.8.30
 * 状压-子集-DP
 * 题目模板：每个子集都有一个花费，求拼成目标子集的最小花费。
 */
